package com.leetcode.剑指offer第2版;

import java.util.Arrays;

/**
 * @author 覃国强
 * @date 2022-05-11 20:15
 */
public class 剑指Offer_40_最小的k个数 {

  static
  class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
      if (arr == null || arr.length == 0 || k >= arr.length) {
        return arr;
      }

      if (k <= 0) {
        return new int[0];
      }

      int[] answer = Arrays.copyOf(arr, k);
      buildMaxHeap(answer);
      for (int i = k; i < arr.length; ++i) {
        if (arr[i] < answer[0]) {
          answer[0] = arr[i];
          maxHeapify(answer, 0);
        }
      }

      return answer;
    }

    private void buildMaxHeap(int[] arr) {
      for (int i = (arr.length - 2) / 2; i >= 0; --i) {
        maxHeapify(arr, i);
      }
    }

    private void maxHeapify(int[] arr, int i) {
      int left = 2 * i + 1;
      int right = 2 * i + 2;
      int target = i;
      if (left < arr.length && arr[left] > arr[target]) {
        target = left;
      }
      if (right < arr.length && arr[right] > arr[target]) {
        target = right;
      }
      if (target != i) {
        swap(arr, i, target);
        maxHeapify(arr, target);
      }
    }

    private void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }

  }


}
